'''VERSION 1.0'''
import networkx as nx
import sys
import pp
import time
import thread

LIMIT = int(sys.argv[3])

def elements_in_bin(binary):
    return [len(bin(binary)[2:]) - i -1 for i in range(len(bin(binary)[2:])) if bin(binary)[2:][i] == '1']

def distribute(nitems, nprocs=None):
    """
        :param nitems: the number of items to be distributed
        :type nitems: int
        :param nprocs: the number of processors available
        :type nprocs: int
        :returns: a list of index tuples (imin, imax)
        defining the slices of the input sequence
        to be handled by each processor
        :rtyoe: list
        """
    if nprocs is None:
        nprocs = default_nprocs
    nitems_per_proc = (nitems+nprocs-1)/nprocs
    return [(i, min(nitems, i+nitems_per_proc))
            for i in range(0, nitems, nitems_per_proc)]


def divide_and_conquer(n):
    if n == 0:
        return [0]
    if n < LIMIT:
        return [0,n]
    steps = n/LIMIT
    if steps < 1:
        return [0,n]
    divs = [int(i*LIMIT) for i in range(steps + 1) if i*LIMIT < n]
    divs.append(n)
    return divs

'''
    Parallelized function
'''
def process_itemsets(items,border,faces):
    results = []
    belim = set([])
    for item in items:
        # calculate candidates
        candidates = set([])
        for b in border:
            a = item & b
            #if a not in candidates:
            candidates.add(a)
        
        # CHECK CANDIDATES' FACES
        for c in candidates:
            f =  faces.get(c,0)
            if item & f == 0:
                results.append((item,c))
                if c in border:
                    belim.add(c*-1)
                faces[c] = f | (item & (item ^ c))
                border.add(item)
    return border.union(belim),faces,results



def order_bins(cands):
    b = [(sum([int(j) for j in bin(i)[2:]]),i) for i in cands]
    b.sort(reverse=True)
    return [i[1] for i in b]

class Concept:
    def __init__(self,intent,id):
        self.intent = intent
        self.support = 0
        self.id = id
        self.bin_intent()
    
    def bin_intent(self):
        self.bin = 0
        for i in intent:
            self.bin += 1 << int(i)

def initialize_node(conc,g):
    g.add_node(conc.id, intent=conc.bin,intt=str(conc.intent).replace('[','').replace(']','').replace("'",'').replace(' ',''),support = conc.support)

path = sys.argv[2]
file = open(path,'r')

# the output lattice is modeled as a directed graph
g = nx.DiGraph()
# inverted index from binary representations to the formal concepts
inv_idx = {} 
# Level-wise ordered concepts 
latidx = {} 

'''
    BEGIN READING ITEMSETS
'''
for line in file:
    line = line.replace('\n','')
    intent = line.split()
    sup = intent[len(intent)-1]
    intent = intent[:len(intent)-1]
    conc = Concept(intent,len(g.node))
    conc.support = int(sup.replace('(','').replace(')',''))
    if len(intent) not in latidx:
        latidx[len(intent)] = []
    latidx[len(intent)].append(conc.bin)
    initialize_node(conc,g)
    inv_idx[conc.bin] = conc

# Concepts have to be processed from lower to higher levels
nums = latidx.keys()
nums.sort()

ppservers = ()

if len(sys.argv) > 2:
    ncpus = int(sys.argv[1])
    # Creates jobserver with ncpus workers
    job_server = pp.Server(ncpus, ppservers=ppservers)
else:
    # Creates jobserver with automatically detected number of workers
    job_server = pp.Server(ppservers=ppservers)

print "Starting pp with", job_server.get_ncpus(), "workers"

class Unifier():
    def __init__(self):
        self.border = set([0])
        self.newborder = set([])
        self.faces = {}
        self.arcs = []
        self.lock = thread.allocate_lock()
    
    def unify(self,input):
        self.lock.acquire()
        for b in input[0]:
            self.newborder.add(b)
        for c in input[1]:
            self.faces[c] = self.faces.get(c,0) | input[1][c]
        self.arcs.extend(input[2])
        self.lock.release()

    def update(self):
        self.border = set([i for i in self.newborder if (-1*i) not in self.newborder])
        self.newborder = set([])
        


start_time = time.time()

border = [0]
faces = {}
un = Unifier()
i = 0
r = 0
for n in nums:
    # each layers have to be processed sequentially
    if n != 0:
        # a layer is divided in several subtask (4 in this case)
        
        calcul_time_0 = time.time()
        divs = divide_and_conquer(len(latidx[n]))
        jobs =  [job_server.submit(process_itemsets, (latidx[n][divs[d]:divs[d+1]],un.border,un.faces),callback = un.unify) for d in range(len(divs)-1)]
        '''
        if len(latidx[n]) > 80:
            slices = distribute(len(latidx[n]),ncpus)
            jobs = [job_server.submit(process_itemsets, (latidx[n][slice[0]:slice[1]],un.border,un.faces),callback = un.unify) for slice in slices]
        else:
            jobs = [job_server.submit(process_itemsets, (latidx[n],un.border,un.faces),callback = un.unify)]
        '''
        job_server.wait()
        calcul_time_1 = time.time()
        un.update()
        calc_time = calcul_time_1 - calcul_time_0
        int_time = time.time() - calcul_time_1
#        print "Layer",n,':',(calc_time),'/',len(latidx[n]),'||',(int_time),'==',(calc_time + int_time),len(un.border)
        print n,' & ',len(latidx[n]),' & ',r,' & ',round(calc_time,5),' & ',(round(int_time,5)),' & ',round((calc_time + int_time),5),'\\\\'
        r = len(un.border)

for arc in un.arcs:
    #print ([len(bin(arc[0])[2:]) - i -1 for i in range(len(bin(arc[0])[2:])) if bin(arc[0])[2:][i] == '1'],[len(bin(arc[1])[2:]) - i -1 for i in range(len(bin(arc[1])[2:])-1,-1,-1) if bin(arc[1])[2:][i] == '1'])
    g.add_edge(inv_idx[arc[0]].id,inv_idx[arc[1]].id)

job_server.print_stats()
for n in g.nodes():
    del g.node[n]['intent'] # Intent contains too much information, is eliminated from the output
nx.write_gml(g,"lattice.gml")
ug = g.to_undirected()
